You are given an empty 2D binary grid grid of size m x n. The grid represents a map where 0's represent water and 1's represent land. Initially, all the cells of grid are water cells (i.e., all the cells are 0's).
We may perform an add land operation which turns the water at position into a land. You are given an array positions where positions[i] = [ri, ci] is the position (ri, ci) at which we should operate the ith operation.
Return an array of integers answer where answer[i] is the number of islands after turning the cell (ri, ci) into a land.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]] Output: [1,1,2,3] Explanation: Initially, the 2d grid is filled with water. - Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land. We have 1 island. - Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land. We still have 1 island. - Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land. We have 2 islands. - Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land. We have 3 islands.
Example 2:
Input: m = 1, n = 1, positions = [[0,0]] Output: [1]
Constraints:
1 <= m, n, positions.length <= 1041 <= m * n <= 104positions[i].length == 20 <= ri < m0 <= ci < n
Follow up: Could you solve it in time complexity O(k log(mn)), where k == positions.length?
Average Rating: 4.19 (21 votes)
Approach #1 (Brute force) [Time Limit Exceeded]
Algorithm
Reuse the code for Problem 200: Number of Islands, for each addLand operation, just call the numIslands function of Problem 200 to get the number of islands after performing that operation.
Complexity Analysis
-
Time complexity : O(L×m×n) where L is the number of operations, m is the number of rows and n is the number of columns.
-
Space complexity : O(m×n) for the
gridandvisited2D arrays.
Approach #2: (Ad hoc) [Accepted]
Algorithm
Use a HashMap to map index of a land to its island_ID (starting from 0).
For each addLand operation at position (row, col), check if its adjacent neighbors are in the HashMap or not and put the island_ID of identified neighbors into a set (where each element is unique):
-
if the
setis empty, then the new land at position (row, col) forms a new island (monotonically increasing island_ID by 1); -
if the
setcontains only one island_ID, then the new land belongs to an existing island and island_ID remains unchanged; -
if the
setcontains more than one island_ID, then the new land bridges these separate islands into one island, we need to iterate through theHashMapto update this information (time consuming!) and decrease the number of island appropriately.
Complexity Analysis
-
Time complexity : O(L2), for each operation, we have to traverse the entire HashMap to update island id and the number of operations is L.
-
Space complexity : O(L) for the
HashMap.
P.S. C++ solution was accepted with 1409 ms runtime, but Java solution got an TLE (Time Limit Exceeded).
Approach #3: Union Find (aka Disjoint Set) [Accepted]
Intuition
Treat the 2d grid map as an undirected graph (formatted as adjacency matrix) and there is an edge
between two horizontally or vertically adjacent nodes of value 1, then the problem reduces to finding the number of connected components in the graph after each addLand operation.
Algorithm
Make use of a Union Find data structure of size m*n to store all the nodes in the graph and initially each node's parent value is set to -1 to represent an empty graph. Our goal is to update Union Find with lands added by addLand operation and union lands belong to the same island.
For each addLand operation at position (row, col), union it with its adjacent neighbors if they belongs to some islands, if none of its neighbors belong to any islands, then initialize the new position as a new island (set parent value to itself) within Union Find.
For detailed description of Union Find (implemented with path compression and union by rank), you can refer to this article.
Complexity Analysis
-
Time complexity : O(m×n+L) where L is the number of operations, m is the number of rows and n is the number of columns. it takes O(m×n) to initialize UnionFind, and O(L) to process positions. Note that Union operation takes essentially constant time[1] when UnionFind is implemented with both path compression and union by rank.
-
Space complexity : O(m×n) as required by UnionFind data structure.
Footnotes
Last Edit: June 16, 2019 9:58 AM
There is a bug for the third approach when we add the same position to the matrix.
I suggest we can check the duplicate in the setParent function
Like below:
void setParent(int i) {
if (parent[i] == -1)
{
parent[i] = i;
++count;
}
}
August 19, 2019 4:04 AM
The Union-Find solution can be just O(L) if you don't initialize the data structure upfront and do it only on demand--in my implementation when I move to a new position in the list I initialize it (with parent and rank) in the data structure, and if a node does not exist in the parent dict it is assumed to be a zero/water.
August 8, 2018 6:50 AM
We can use a hashset to record all lands in approach 3 to avoid O(mn) initialization of disjoint set.
Last Edit: January 2, 2020 9:59 AM
Hmmm.... any solution hitting O(klog(mn))?
December 31, 2018 2:45 AM
boolean[][] visited = new boolean[nr][nc];
for (boolean[] row : visited) {
Arrays.fill(row, false);
}
this is not needed, since a boolean array by default has false in it
Last Edit: April 18, 2020 8:34 PM
Solution 2 is incorrect for duplicate position test case.
3
3
[[0,0],[0,1],[1,2],[1,2]]
add this block to line 12
if (land2id.containsKey(r * n + c)) {
result.add(num_islands);
continue;
}
July 1, 2019 7:33 AM
February 5, 2018 9:30 PM
Create parent[mn+1] and reserve parent[0] to indicate whether a cell is water.
Since the init value of new int[m * n + 1] is 0, you can avoid the array initialization of complexity O(mn).
you can achieve O(klog(mn)).
March 12, 2020 4:58 PM
Recently added test case with duplication position breaks all the solutions.
3
3
[[0,0],[0,1],[1,2],[1,2]]
It is easy to fix for this case (no neighbors), however, if we consider duplication cases with neighbors, and with a different number of them, all the approaches, I believe, should change.
So it the last test case valid with the problem statement?
January 6, 2019 2:53 AM
For Solution #2, I think the complexity should be lower than what was described:
"...if the set contains more than one island_ID, then the new land bridges these separate islands into one island, we need to iterate through the HashMap to update this information (time consuming!) and decrease the number of island appropriately."
If the new position is a land bridge, you do not need to iterate through the entire hash map, but instead just examine at most 4 neighboring positions to update their islandID's to that of a chosen neighbor. That's 4 X O(1) operations, not an O(L) iteration of all keys in the hashtable.
xxxxxxxxxx};class Solution { public: vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) { vector<int> res; roots = vector<int>(m * n, -1); vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int island = 0; for (auto pos : positions) { int x = pos[0], y = pos[1], idx_p = x * n + y; if(roots[idx_p] != -1) { res.push_back(island); continue; } roots[idx_p] = idx_p; ++island; for (auto dir : dirs) { int row = x + dir.first, col = y + dir.second, idx_new = row * n + col; if (row >= 0 && row < m && col >= 0 && col < n && roots[idx_new] != -1) { int rootNew = findRoot(idx_new), rootPos = findRoot(idx_p); if (rootPos != rootNew) { roots[rootPos] = rootNew; --island; } } } res.push_back(island); } return res; } private: vector<int> roots; int findRoot(int idx) { while(idx != roots[idx]) { roots[idx] = roots[roots[idx]]; idx = roots[idx]; } return idx; }};